package org.example.struct.array2;

import com.alibaba.fastjson2.JSON;

/**
 * @author liyishan
 * @date 2023/8/29 10:34
 * @apiNote   同 M04Search
 */

public class Test00034SearchRange {
    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] res = test(nums,target);
        System.out.println(JSON.toJSON(res));
    }

    public static int[] test(int[] nums, int target) {
        int n = nums.length;
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        for(int i=0;i<n;i++){
            if(nums[i] == target){
                res[0] = i;
                break;
            }
        }
        for(int i=n-1;i>=0;i--){
            if(nums[i] == target){
                res[1] = i;
                break;
            }
        }
        return res;
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1,-1};
        int leftIdx =binarySearch(nums,target,true);
        int rightIdx = binarySearch(nums,target,false)-1;
        if(leftIdx <=rightIdx && rightIdx < nums.length && nums[leftIdx] == target){
            res[0] = leftIdx;
            res[1] = rightIdx;
        }
        return res;
    }
    public static int binarySearch(int[] nums,int target,boolean lower){
        int left = 0, right = nums.length - 1,ans =nums.length;
        while(left <= right){
            int mid = (left+right)/2;
            if(nums[mid] > target || (lower && nums[mid] >= target)){
                right = mid - 1;
                ans = mid;
            }else{
                left = mid + 1;
            }
        }
        return ans;
    }

}
